package com.sicheng.lc.杂题.路径问题;

import java.util.ArrayDeque;
import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/16 23:40
 */
public class 网格中的最短路径 {
    //https://leetcode.cn/problems/shortest-path-in-a-grid-with-obstacles-elimination/
    static int[][] d = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};

    static int m, n;
    static int[][] visit = new int[40][40];

    {
        for (int[] v : visit) {
            Arrays.fill(v, -1);
        }
    }


    public int shortestPath(int[][] grid, int k) {
        m = grid.length;
        n = grid[0].length;
        if (m == 1 && n == 1)
            return 0;
        return bfs(grid, visit, k);
    }

    private int bfs(int[][] grid, int[][] visit, int k) {

        int i = 0, j = 0;
        visit[i][j] = k;
        ArrayDeque<int[]> deque = new ArrayDeque<>();
        deque.offer(new int[]{i, j, k});

        int step = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            step++;
            for (int a = 0; a < size; a++) {
                int[] p = deque.poll();
                assert p != null;
                i = p[0];
                j = p[1];
                for (int[] dd : d) {
                    int x = i + dd[0];
                    int y = j + dd[1];
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        if (x == m - 1 && y == n - 1)
                            return step;
                        int ck = p[2] - grid[x][y];
                        // 需要加入一个状态 剩余消除障碍物的次数
                        // 结点是否可以被拓展 首先ck>=0 至少剩余0次消除机会
                        // 当前结点没有被拓展 ，或者本次拓展时剩余机会更多
                        // 逻辑上我们只visit一遍点
                        if (ck >= 0 && (visit[x][y] == -1 || ck > visit[x][y])) {
                            visit[x][y] = ck;
                            deque.offer(new int[]{x, y, ck});
                        }
                    }
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        网格中的最短路径 s = new 网格中的最短路径();
        int[][] g = {
                {0,0,0},
                {1,1,0},
                {0,0,0},
                {0,1,1},
                {0,0,0}
        };
        System.out.println(s.shortestPath(g, 1));
    }
}
